Night Owl 6/Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso/016a/faketo4d.zip/HEAPUNT2.PAS

Pascal/Delphi Source File | 1991-10-05 | 6KB | 187 lines

unit HeapUnt2;

interface

const  MAX=100;

type
     DataType = string;
     HeapType = record
        data: array[1..MAX] of DataType;
        next: integer;
       end;

     HeapObj = object
       Heap: HeapType;

       procedure Init;
       procedure ReHeapUp;
       procedure Insert(num: DataType);
       procedure ReHeapDown;
       function GetMin: DataType;
       function Empty:  Boolean;
       function TotalNum: integer;
       function search(num: DataType): boolean;
       end; { Object HeapObj }

implementation

{==========================================================================}
{ This procedure swaps the two inputs of DataType                          }
{==========================================================================}
procedure swap(var a,b: DataType);

var temp: DataType;

begin   { Procedure Swap }
  temp:=a;
  a:=b;
  b:=temp;
end;   { Procedure Swap }


{==========================================================================}
{ This procedure initializes the Heap.                                     }
{==========================================================================}
procedure HeapObj.Init;

begin   { Procedure Init }
  heap.next:=1;
end;    { Procedure Init }


{==========================================================================}
{ This procedure moves a priority up the heap until it is in the correct   }
{ position; ie, it is less than its children and greater than its parent   }
{==========================================================================}
procedure HeapObj.ReHeapUp;

var done: boolean;
    i:    integer;

begin   { Procedure ReHeapUp }
  done:=false;
  i:=heap.next-1;

  while not done do
   begin
     if heap.data[i div 2] > heap.data[i] then      { if less than parent }
       swap(heap.data[i div 2],heap.data[i])        { swap with its parent }
     else
       done:=true;
     i:=i div 2;                                    { point to parent }
     if i=1 then
       done:=true;
   end; { while }
end;   { Procedure ReHeapUp }


{==========================================================================}
{ This procedure inserts a new priority into the heap and reorders heap    }
{ to maintain its order.                                                   }
{==========================================================================}
procedure HeapObj.Insert(num: DataType);

begin   { Procedure Insert }
  heap.data[heap.next]:=num;                        { put item into last pos. }
  inc(heap.next);                                   { increment next ptr. }

  if heap.next > 2 then                             { re-heap up if needed. }
    ReHeapUp;
end;   { Procedure Insert }


{==========================================================================}
{ This procedure moves a priority down the heap until it is in the correct }
{ position. (Only executed after a deletion from the heap.)                }
{==========================================================================}
procedure HeapObj.ReHeapDown;

var done: boolean;
    i:    integer;

begin   { Procedure ReHeapDown }
  i:=1;
  done:=false;
  while not done do
   begin
    if ( (i*2)+1 < heap.next) and (heap.data[i]<heap.data[i*2])
      and (heap.data[i]<heap.data[(i*2)+1]) then
        done:=true
    else if ( (i*2)+1 >= heap.next) and (heap.data[i]<heap.data[i*2]) then
      done:=true
    else
      begin
       if ( (i*2)+1 < heap.next) and (heap.data[(i*2)+1]<heap.data[i*2]) then
         begin
           swap(heap.data[i],heap.data[(i*2)+1]);      { swap with right child }
           i:=(i*2)+1;
         end { if }
       else
         begin
           swap(heap.data[i],heap.data[i*2]);          { swap with left child }
           i:=i*2;
         end; { if }

       if i>=heap.next div 2 then
         done:= true;
     end; { if }
   end; { while }
end;   { Procedure ReHeapDown }


{==========================================================================}
{ This function returns the minimum priority and reorders the heap to      }
{ maintain its order.                                                      }
{==========================================================================}
function HeapObj.GetMin: DataType;

begin   { Function GetMin }
  GetMin:=heap.data[1];                            { assign min priority }
  dec(heap.next);                                  { decrement next ptr }

  heap.data[1]:=heap.data[heap.next];              { move last element to top }

  if heap.next > 2 then                            { re-heap down if needed }
    ReHeapDown;
end;   { Function GetMin }


{==========================================================================}
{ This procedure tells if the Heap is empty.                               }
{==========================================================================}
function HeapObj.Empty: Boolean;

var temp: boolean;

begin   { Function Empty }
  Empty:=heap.next=1;
end;    { Function Empty }

{==========================================================================}
{ This procedure tells the number of heap elements                         }
{==========================================================================}
function HeapObj.TotalNum: integer;

begin { Function TotalNum }
  TotalNum:=Heap.next-1;
end;  { Function TotalNum }


{==========================================================================}
{ This procedure tells if the item is in the heap.                         }
{==========================================================================}
function HeapObj.search(num: DataType): boolean;

var i:integer;

begin { Function Search }
  search:=false;
  for i:=1 to TotalNum do
    if heap.data[i]=num then
      search:=true;
end;  { Function Search }


begin
end. { unit }